﻿/** 
 * Copyright (c) 2001 University of Maryland, College Park, MD 20742, USA
 * Copyright (c) 2005 In4Arch
 *
 *  The MIT License
 *  Permission is hereby granted, free of charge, to any person obtaining a copy of this 
 *  software and associated documentation files (the "Software"), to deal in the Software 
 *  without restriction, including without limitation the rights to use, copy, modify, merge, 
 *  publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons 
 *  to whom the Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in all copies 
 *  or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 *  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
 *  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
 *  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
 *  CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE 
 *  OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Authors: Benjamin B. Bederson and Martin Wattenberg 2001 
 * http://www.cs.umd.edu/hcil/treemap-history/index.shtml
 * 
 * Author: moedusa moedusa@gmail.com 2005
 * http://moedusa.name/
 *
 * Author: Nikita Shlyakhov shlyakhov@mail.ru 2006
 **/

 
import in4arch.alg.treemap.MapLayout; 
import in4arch.alg.treemap.MapModel; 
import in4arch.alg.treemap.Mappable;
import in4arch.alg.treemap.Rect; 

class in4arch.alg.treemap.StripTreemap implements MapLayout {
	
    private var items_array:Array;
    private var layoutBox:Rect; 
    private var lookahead:Boolean = true;

    public function layout(model:MapModel, bounds:Rect):Void {
		
		items_array = model.getItems();
		layoutBox = bounds;
	
		var totalSize:Number = 0;
		for (var i = 0; i < items_array.length; i++) {
			totalSize += items_array[i].getSize();
		}
		var area:Number = layoutBox.w * layoutBox.h;
		var scaleFactor:Number = Math.sqrt(area / totalSize);
	
		var finishedIndex:Number = 0;
		var numItems:Number = 0;
		var prevAR:Number = 0;
		var ar:Number = 0;
		var height:Number;
		var yoffset:Number = 0;
		var box:Rect = new Rect(layoutBox.x, layoutBox.y, layoutBox.w, layoutBox.h);
		box.x = box.x / scaleFactor;
		box.y = box.y / scaleFactor;
		box.w = box.w / scaleFactor;
		box.h = box.h / scaleFactor;
		
		while (finishedIndex < items_array.length) {
			// Layout strip
			numItems = layoutStrip(box, finishedIndex);
			
			// Lookahead to second strip
			if (lookahead) {
				if ((finishedIndex + numItems) < items_array.length) {
					var numItems2:Number;
					var ar2a:Number;
					var ar2b:Number;
					// Layout 2nd strip and compute AR of first strip plus 2nd strip
					numItems2 = layoutStrip(box, finishedIndex + numItems);
					ar2a = computeAverageAspectRatio(finishedIndex, numItems + numItems2);
					// Layout 1st and 2nd strips together
					computeHorizontalBoxLayout(box, finishedIndex, numItems + numItems2);
					ar2b = computeAverageAspectRatio(finishedIndex, numItems + numItems2);
					
					if (ar2b < ar2a) {
					 numItems += numItems2;
					} else {
					 computeHorizontalBoxLayout(box, finishedIndex, numItems);
					}
				}
			}
	
			for (var i = finishedIndex; i < (finishedIndex+numItems); i++) {
			     items_array[i].getRect().y += yoffset;
			}
			
			height = items_array[finishedIndex].getRect().h;
			yoffset += height;
			box.y += height;
			box.h -= height;
	
			finishedIndex += numItems;
		}
	
		var rect:Rect;
		for (var i=0; i<items_array.length; i++) {
			rect = items_array[i].getRect();
			rect.x = rect.x*scaleFactor;
			rect.y = rect.y*scaleFactor;
			rect.w = rect.w*scaleFactor;
			rect.h = rect.h*scaleFactor;
			
		    rect.x += bounds.x;
			rect.y += bounds.y;
			items_array[i].setRect(rect);
		}
    }

    private function layoutStrip(box:Rect, index:Number):Number {
	 var numItems:Number = 0;
	 var prevAR:Number;
	 var ar:Number = Number.MAX_VALUE;
	 var height:Number;
	 
		do {
			prevAR = ar;
			numItems++;
			height = computeHorizontalBoxLayout(box, index, numItems);
			ar = computeAverageAspectRatio(index, numItems);
		} while ((ar < prevAR) && ((index + numItems) < items_array.length));
		
		if (ar >= prevAR) {
			numItems--;
			height = computeHorizontalBoxLayout(box, index, numItems);
			ar = computeAverageAspectRatio(index, numItems);
		}
		
	 return numItems;
    }

    private function computeHorizontalBoxLayout(box:Rect, index:Number, numItems:Number):Number {
		var totalSize:Number = computeSize(index, numItems);
		var height:Number = totalSize / box.w;
		var width:Number;
		var x:Number = 0;
		
		for (var i=0; i<numItems; i++) {
			width = items_array[i+index].getSize() / height;
			items_array[i+index].setNRect(x, 0, width, height);
			x += width;
		}
	
		return height;
    }

    private function computeSize(index:Number, num:Number):Number {
		var size:Number = 0;
		for (var i=0; i<num; i++) {
			size += items_array[i+index].getSize();
		}
		return size;
    }

    private function computeAverageAspectRatio(index:Number, numItems:Number):Number {
		var ar:Number;
		var tar:Number = 0;
		var w:Number;
		var h:Number;
		for (var i=0; i<numItems; i++) {
			var tmp:Mappable = items_array[i+index];
			w = tmp.getRect().w;
			h = tmp.getRect().h;
			ar = Math.max((w / h), (h / w));
			tar += ar;
		}
		tar = tar / numItems;
		return tar;
    }

    private function computeAspectRatio(index:Number):Number {
		var w:Number = items_array[index].getRect().w;
		var h:Number = items_array[index].getRect().h;
		var ar:Number = Math.max((w / h), (h / w));
		return ar;
    }
	
    public function getName():String {
	 return "StripTreemap";
    }

    public function getDescription():String {
	 return "An Ordered Squarified Treemap";
    }
	
    public function setLookahead(lookahead:Boolean):Void {
	    this.lookahead = lookahead;
    }
	
}